本发明公开了用于还击故障攻击的方法和设备。将RSA密钥的公共指数e嵌入缺少该指数的RSA密钥对象中。在求幂期间,可以提取公共指数e并使用公共指数e来验证求幂结果是正确的。仅在这种情况下才输出该结果。本发明对故障攻击进行还击。本发明还提供了一种装置(100)和一种计算机程序产品(140)。
1.一种用于计算求幂的方法,所述方法是抗故障攻击的,并包括在设备(100)中进行的以下步骤:获得RSA私有密钥对象,所述RSA私有密钥对象与匹配的公共指数相关联;获得使用所述RSA私有密钥对象的求幂的结果;获得所述匹配的公共指数;以及使用所述匹配的公共指数来验证求幂的结果是正确的;所述方法的特征在于:在标准模式中:所述RSA私有密钥对象包括RSA模N,所述匹配的公共指数e是从其所嵌入的所述RSA模N中提取获得的;以及在CRT模式中:所述RSA私有密钥对象包括所述RSA模N的因数,所述匹配的公共指数e是从所述RSA模N的一个因数提取获得的或者是从所述RSA模N的因数的乘积提取获得的。
2.根据权利要求1所述的方法,其中所述匹配的公共指数e被包括在RSA模N的二进制表示的前端比特中。
3.根据权利要求2所述的方法,其中在CRT模式中,所述RSA模N是通过将所述RSA模N的因数相乘来获得的。
4.一种用于计算求幂的设备(100),所述设备(100)是抗故障攻击的,并包括:用于获得RSA私有密钥对象的装置(120),所述RSA私有密钥对象与匹配的公共指数相关联;用于获得使用所述RSA私有密钥对象的求幂的结果的装置(120);以及用于使用所述匹配的公共指数验证求幂的结果正确的装置(120);所述设备的特征在于包括用于获得所述匹配的公共指数e的装置(120):在标准模式中,所述匹配的公共指数e是从在所述RSA私有密钥对象中包括的RSA模N提取获得的;以及在CRT模式中,所述匹配的公共指数e是从所述RSA模N的一个因数提取获得的或者是从所述RSA模N的因数的乘积提取获得的,所述RSA模N的因数或所述RSA模N的因数的乘积被包括在所述RSA私有密钥对象中。
5.根据权利要求4所述的设备,其中用于获得RSA私有密钥对象的装置、用于获得使用所述RSA私有密钥对象的求幂的结果的装置、用于使用所述匹配的公共指数验证求幂的结果正确的装置、以及用于获得所述匹配的公共指数e的装置是在至少一个处理器(120)上实现的。技术领域
本发明总体涉及密码术,具体涉及RSA的故障攻击对策。
背景技术
本部分意在向读者介绍本领域中可能与下面描述和/或要求保护的本发明各个方面相关的各个方面。相信该讨论有助于向读者提供背景信息以便于更好地理解本发明的各个方面。相应地,应当理解,要从这种角度来阅读这些论述,而不是作为对现有技术的引入。故障攻击打乱了安全设备的预期行为并使其不正常工作,以从故障输出中推断敏感数据。Bonehxa0etxa0al.在“Onxa0thexa0importancexa0ofxa0CheckingCryptographicxa0Protocolsxa0forxa0Faults”;D.Boneh,R.A.Demillo,andxa0R.J.Lipton;Inxa0W.Fumy,editor,Advancesxa0inxa0Cryptology-EUROCRYPT’97,volumexa01233xa0ofxa0Lecturexa0Notesxa0inxa0Computerxa0Science,pagesxa037-51,Springer-Verlagxa01997中介绍了这种攻击。故障攻击可能是非常强有力的。例如,具有单一随机故障且使用中国剩余(CRT)而评估的故障RSA签名可以允许攻击者从故障签名中恢复完整的秘密密钥。因此,很清楚,必须采取对策。RSA是基于难以对大素数的乘积进行因数分解的事实的。令N=pq为两个大素数的乘积。我们令e和d表示一对匹配的公共和私有指数,满足ed≡1(modλ(N)),同时gcd(e,λ(N))=1并且λ是Carmichael函数。由于N=pq,因此我们有λ(N)=lcm(p-1,q-1)。给定xexa0modxa0N。然后,给定y,则相应的私有运算(例如对密码文本的解密或者签名的产生)是计算y^dxa0modxa0N。从e和d的定义中,我们明显得到y^d≡x(modN)。可以通过中国剩余(CRT模式)来高速执行私有运算。独立地执行模p和q的计算,然后重新组合。在这种情况中,私有参数是{p,q,d_p,d_q,i_q},其中d_p=dxa0mod(p-1)、d_q=dxa0mod(q-1)并且i_q=q^-1xa0modxa0p。然后我们得到y^dxa0modxa0N为CRT(x_p,x_q)=x_q+q[i_q(x_p-x_q)modxa0p],其中x_p=y^dpmodxa0p并且x_q=y^dqxa0modxa0q。当然,已经提出了几种这样的对策。在USxa05991415中公开了由Shamir提出的最初对策,最初在EUROCRYPT’97的残余议会(RumpSession)提出的。上提出。稍作简化地,该方法引入随机值j并使用(modxa0j*p)而不是(modxa0p)来进行计算,并验证是否到达预期值;作为给定的示例,如果j是32比特长,则在故障之后两个值匹配的可能性是2^-32=1/4,294,967,296,所以风险是非常小的。更具体地,首先计算x’_p=y^dxa0modxa0j*p和x_j=y^dxa0modxa0j的值。验证x’_p≡x_j(modxa0j),并且如果是这样,则假定计算是无差错的。然后由x_p=x’_pxa0modxa0p给出求幂模p的结果。对于模q也是同样的。对策的正确性依赖于以下观察:对于任何正整数j,xxa0modxa0p=(xxa0modxa0j*p)modxa0p。由Kaliski和Robshaw在ftp://ftp.rsasecurity.com/pub/pdfs/bulletn5.pdf中提到的另一种方法在于以通常的方式来进行求幂以获得x=y^dxa0modxa0N,但是在发出x之前,通过检查x^e是否等于y模N来检验其是正确的。所有后续方法基本上依赖于由Shamir提出的方法。这些方法包括:-M.Joye,P.Paillier,andxa0S-M.Yen.Securexa0evaluationxa0ofxa0ModularFunctions.Inxa0R.J.Hwangxa0andxa0C.K.Wu,editors,2001xa0InternationalWorkshopxa0ofxa0Cryptologyxa0andxa0Networkxa0Security,pagesxa0227-229,Taipei,Taiwan,2001.-C.Aumüler,P.Bier,W.Fischer,P.Hofreiter,andxa0J-P.Seifert.FaultAttackxa0onxa0RSAxa0withxa0CRT:Concretexa0Resultsxa0andxa0PracticalCountermeasures.Inxa0B.S.Kaliskixa0Jr.,C.K.Kocxa0andxa0C.Paar,editors,Cryptographicxa0Hardwarexa0andxa0Embeddedxa0Systems-CHESxa02002,volumexa02523xa0ofxa0Lecturexa0Notesxa0inxa0Computerxa0Science,pagesxa0260-275,Springer,2002.-J.ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="197"/>M.Otto,andxa0J-P.Seifert.Axa0Newxa0CRT-RSAxa0AlgorithmSecurexa0Againstxa0Bellcorexa0Attack.Inxa010^thxa0ACMxa0Conferencexa0onComputerxa0andxa0Communicationxa0Security(CCSxa02003),pagesxa0311-320,ACMxa0Press,2003.-M.Cietxa0andxa0M.Joye.Practicalxa0Faultxa0Countermeasuresxa0forxa0ChineseRemainderingxa0basedxa0RSA.Inxa02^ndxa0Workshopxa0Faultxa0Diagnosisxa0andTolerancexa0inxa0Cryptography-FDTCxa02005),pagesxa0124-132,2005.-C.H.Kimxa0andxa0J.-J.Quisquater.Howxa0Canxa0Wexa0Overcomexa0Bothxa0SideChannelxa0Analysisxa0andxa0Faultxa0Attacksxa0onxa0RSA-CRT?Inxa04^thxa0Workshoponxa0Faultxa0Diagnosisxa0andxa0Tolerancexa0inxa0Cryptography-FDTCxa02007,pagesxa021-29,IEEExa0Computerxa0Societyxa0Press,2007.这些方法当中,ntent="drawing" img-format="tif" inline="yes" orientation="portrait" wi="190"/>等人和Ciet等人的方法不提供完全的防篡改。此外,这些方法都没有保证对故障的100%检测,并且这些方法都对性能(运行时间和存储需求)造成冲击,在一些情况下还对个人化过程造成冲击。因此,应当理解,需要一种在RSA上针对故障攻击的对策,检测所有故障。本发明提供了这种解决方案。
发明内容
在第一方面,本发明涉及一种用于计算求幂的方法。所述方法是抗故障攻击的。获得与匹配的公共指数相关联的RSA私有密钥对象。获得使用所述RSA私有密钥对象的求幂的结果。使用匹配的公共指数来验证求幂的结果是正确的。在标准模式中,所述RSA私有密钥对象包括RSA模N,并且所述匹配的公共指数e是从所述RSA模N获得的;在CRT模式中,所述RSA私有密钥对象包括所述RSA模N的因数,并且所述匹配的公共指数e是从所述RSA模N的至少一个因数获得的。在第一优选实施例中,所述匹配的公共指数e被包括在RSA模N的二进制表示的前端比特中。在第二优选实施例中,在CRT模式中,所述匹配的公共指数e被包括在RSA模N的二进制表示的前端比特中,所述RSA模N是通过将所述RSA模N的因数相乘来获得的。在第二方面,本发明涉及一种用于计算求幂的设备,所述设备是抗故障攻击的。所述设备包括:用于获得RSA私有密钥对象的装置,所述RSA私有密钥对象与匹配的公共指数相关联;用于获得使用所述RSA私有密钥对象的求幂的结果的装置;以及用于使用所述匹配的公共指数验证求幂的结果正确的装置。所述设备还包括用于获得所述匹配的公共指数e的装置:在标准模式中,所述匹配的公共指数e是从在所述RSA私有密钥对象中包括的RSA模N获得的;以及在CRT模式中,所述匹配的公共指数e是从所述RSA模N的至少一个因数获得的,所述RSA模N的因数被包括在所述RSA私有密钥对象中。在第一优选实施例中,用于获得RSA私有密钥对象的装置、用于获得使用所述RSA私有密钥对象的求幂的结果的装置、用于使用所述匹配的公共指数验证求幂的结果正确的装置、以及用于获得所述匹配的公共指数e的装置是在至少一个处理器上实现的。在第三方面,本发明涉及一种计算机程序产品,具有存储于其上的指令,当处理器执行所述指令时,所述指令执行第一方面的方法。
附图说明
现在将参照附图,通过非限制性示例,来描述本发明的优选特征,附图中:图1示出了根据本发明的优选实施例的设备。
具体实施方式
在RSA中的“密钥”与“密钥对象”之间存在差异。密钥是可用于密码计算的实体,例如公共密钥(N,e)或私有密钥(N,d)(在CRT模式中分别是(p,q,d_p,d_q,i_q)),而密钥对象可以被说成是密钥的表示。在现有的应用编程接口(API)(例如JavaCards提供的)中,在CRT模式中从{p,q,d_p,d_q,i_q}初始化RSA私有密钥对象,并在标准模式中从{N,d}初始化RSA私有密钥对象。值得注意的是,相应的公共指数e是不可用的。因此,本文已经提到的很多提出的对策检验计算y:=x^dxa0modxa0N是否是无差错的。然而,如果e的值可用,则容易通过验证在标准模式中是否有y^e≡x(modxa0N)或在CRT模式中是否有y^e≡x(modxa0{p,q})来检验y的正确性。当几乎始终选择小的e值时(典型地,3或2¹⁶+1),这尤其正确。为了允许这一点,在优选实施例中,通过将e的值嵌入RSA私有密钥对象中来使e的值可用。与现有技术解决方案相反,这能够检测所有差错。因此,本发明的主要思想是将公共RSA指数e的表示嵌入RSA密钥中。“表示”意味着一种明确地指示值的方式。例如,常用的公共RSA指数是3和2¹⁶+1。这些值的表示的示例是它们的二进制值、它们的字节长度之后是它们的值、或者在事先已达成协议的情况下用“1”代表3并用“2”代表2¹⁶+1。如上所述,从CRT模式下的{p,q,d_p,d_q,i_q}以及从标准模式下的{N,d}获得这种密钥对象。当计算y=x^dxa0modxa0N时,检验是否将公共指数e嵌入RSA密钥的表示中。如果是,则恢复公共指数e。然后验证在标准模式中是否有y^e≡x(modxa0N)或者在CRT模式中是否有y^e≡x(mod{p,q})。仅当验证成功时才返回y。技术人员将理解,RSA模作为随机比特串而出现。因此,优选地,允许应用在“常规”RSA模(即不嵌入公共指数e的模)与根据本发明的模之间进行区分。为此,优选地,在公共指数e之前(或者甚至在之后)插入例如64比特的指示器S(例如“5A5A5A5A5A5A5A5A”),优选地以L|V(长度-值)格式来插入该指示器S,其中L表示公共指数e的值V的长度(例如,以字或比特表示)。给定公共指数e和长度I,可以用包括S、L和V在内的预定部分来产生I比特RSA模N=pq。可以通过任何适当的方法来产生这种模,例如在“M.Joye,RSAxa0Modulixa0Withxa0axa0Predeterminedxa0Portion:Techniquesandxa0Applications.Inxa0Informationxa0Securityxa0Practicexa0andxa0Experience(ISPECxa02008),vol.4991xa0ofxa0Lecturexa0Notesxa0inxa0Computerxa0Science,pages116-130,Springer,2008”和“A.Lenstra.Generatingxa0RSAxa0Modulixa0Withxa0aPredeterminedxa0Portion.Inxa0Advancesxa0inxa0Cryptology-ASIACRYPT‘98,vol.1514xa0ofxa0Lecturexa0Notesxa0inxa0Computerxa0Science,pagesxa01-10,Springer,1998.”中描述的方法。从这种模N,容易恢复公共指数e的值。对应地,在CRT模式中,从乘积pq中恢复公共指数e的值,其中p和q表示N的私有因数。换言之,为了计算求幂,通过例如从一个或多个所存储的数据域中提取私有密钥对象,或者通过从一个或多个所存储的数据域中的值进行计算,或者通过它们的组合,来获得RSA私有密钥对象。RSA私有密钥对象与匹配的公共指数相关联,即,存在例如可用于验证求幂和签名的相应公共指数。例如,通过计算或通过从另一设备接收来获得使用RSA私有密钥对象的求幂的结果,例如y:=x^dxa0modxa0N。然后使用匹配的公共指数来验证求幂结果是正确的,例如通过检验y^e≡x(modN)。根据实施方式,以不同方式获得匹配的公共指数e。在标准模式中,从RSA模N获得,而在CRT模式中,从RSA模N的至少一个因数获得。“获得”意味着提取出嵌入另一实体中的公共指数e。例如在标准模式中,可以将公共指数e形成为N的二进制表示中的一系列二进制数字;而在CRT模式中,可以将公共指数e形成为p或q或者甚至p和q的乘积的二进制表示中的一系列二进制数字。在后者的情况下,必须在能够提取e之前计算该乘积。图1示出了根据本发明的优选实施例的设备。设备100包括适于与其他设备(未示出)进行通信的至少一个接口单元110、至少一个处理器120以及适于存储数据(例如中间计算结果)的至少一个存储器130。处理器120适于从RSA私有密钥对象中提取嵌入的公共指数e,计算求幂,并使用公共指数e来验证结果,如本文前述那样。计算机程序产品140(例如CD-ROM或DVD)包括所存储的指令,当处理器120执行该指令时,该指令执行根据本发明的任何实施例所述的方法。应当理解,本发明使得能够对所有故障和差错进行检测。还应当理解,本发明与现有的实施方式完全兼容,所以不需要改变API。最后,另一个优点在于本发明的方法非常高效;典型地,本发明的方法仅需要少数附加的模乘法,所以,用于典型2048比特应用的验证步骤仅代表总体计算的大约0.09%至0.5%。可以独立地或者以任何适当组合来提供说明书以及(在适当时)权利要求和附图中公开的每一个特征。还可以以软件来实现被描述为以硬件实现的特征,反之亦然。连接(在适当时)可以被实现为无线连接或有线(但不必是直接或专用的)连接。在权利要求中出现的参考标记仅作示意之用,而不应对权利要求的范围有限制效果。